package com.yj.springbootdesign.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * 动态规划：最优子结构，边界，状态转移
 * 台阶问题
 * 有10层台阶，每次可以上1层或者2层，一共有多少中走法
 * F(n) = F(n-1) + F(n-2)  (n>=3)
 */
public class Algorithm01 {

    static Map<Object,Object> map = new HashMap<>();

    public static void main(String[] args) {
        int sum = up2(4);
        System.out.println(sum);
    }

    // 时间复杂度 2^n



    public static int up(int num){
        if (num <= 0){
            return 0;
        }
        if (num == 1){
            return 1;
        }
        if (num == 2){
            return 2;
        }
            return  up(num-1) + up(num -2);
    }

    // 利用map 将重复计算的数据保存起来，减少时间复杂度
    public static int up1(int num){
        if (num <= 0){
            return 0;
        }
        if (num == 1){
            return 1;
        }
        if (num == 2){
            return 2;
        }

        if (map.containsKey(num)){
            return (int) map.get(num);
        }else {
            int value = up1(num-1) + up1(num -2);
            map.put(num,value);
            return value;
        }
    }

    // 利用 F(n) = F(n-1) + F(n-2) n>=3 
    public static int up2(int num){
        if (num <= 0){
            return 0;
        }
        if (num == 1){
            return 1;
        }
        if (num == 2){
            return 2;
        }
        int temp = 0;
        int a = 1;
        int b = 2;

        for (int i = 3; i <= num ; i++) {
            temp = a + b;
            a = b;
            b = temp;
        }
        return temp;
    }
}
